/**
 * 归并排序-> 先分成最小的有序数组，在逐个合并成更大的有序数组
 * 时间复杂度
 * 1. 先分  O(logN)
 * 2. 再并 O(N)
 * 时间复杂度 O(N*logN)
 * 
 */
const assert = require('assert')
const mergeSort = (list) =>{
    const rec = (arr) => {
        if (arr.length === 1) {
            return arr
        }
        const mid = Math.floor(arr.length / 2)
        const leftArr = arr.slice(0, mid)
        const rightArr = arr.slice(mid)
        const left = rec(leftArr)
        const right = rec(rightArr)
        console.log('rec', left, right);
        let res = []
        while (left.length > 0 || right.length > 0) {
            if (left.length > 0 && right.length > 0) {
                res.push(left[0] < right[0] ? left.shift() : right.shift())

            } else if (left.length) {
                res.push(left.shift())
            } else if (right.length) {
                res.push(right.shift())
            }
        }
        return res
    }
    return rec(list)
}

const arr = [3,2,1,0, -1]
const newArr = mergeSort(arr)
console.log(newArr);
assert.deepStrictEqual(newArr, [-1, 0,1,2,3])